package xyf.p04.tree;

import commons.TreeNode;

/**
 * ClassName: M0406_InOrderSuccessor
 * Description:
 * Author: xyf
 * Date: 9/8/22 6:16 PM
 * Version: 1.0
 **/
public class M0406_InOrderSuccessor
{
    private TreeNode res = null;

    private boolean isComing = false;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p)
    {
        dfs(root, p);
        return res;
    }

    private void dfs(TreeNode root, TreeNode p)
    {
        if (root == null)
        {
            return;
        }

        dfs(root.left, p);

        if (isComing)
        {
            res = root;
            isComing = false;
            return;
        }

        if (root == p)
        {
            isComing = true;
        }


        dfs(root.right, p);
    }
}